package com.pan.alg.niuke.tree;

import com.google.common.collect.Queues;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 描述
 * 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 *
 * 该二叉树层序遍历的结果是
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 *
 *
 * 提示:
 * 0 <= 二叉树的结点数 <= 1500
 */
public class TreeNodeLevelOrder {

    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> vals = new ArrayList<>();
        if(null==root){
            return vals;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        while(!queue.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                level.add(poll.val);
                if(null!=poll.left){
                    queue.add(poll.left);
                }
                if(null!=poll.right){
                    queue.add(poll.right);
                }

            }
            vals.add(level);
        }
        return vals;
    }
}
